package demo9;

public class Solution {
    //1.剑指 Offer II 052. 展平二叉搜索树(dfs)
    private TreeNode dummy = new TreeNode(-1);
    private TreeNode prev = dummy;//作为上一个结点
    public TreeNode increasingBST(TreeNode root) {
        createTree(root);
        return dummy.right;
    }
    private void createTree(TreeNode root) {
        if(root == null) {
            return;
        }
        createTree(root.left);
        prev.right = root;
        prev = root;
        root.left = null;
        createTree(root.right);
    }
    //2.剑指 Offer II 059. 数据流的第 K 大数值(优先级队列)
    class KthLargest {
        private PriorityQueue<Integer> queue;
        private int k;
        public KthLargest(int k, int[] nums) {
            this.k = k;
            this.queue = new PriorityQueue();
            for(int i = 0; i < nums.length; i++) {
                if(i < k) {
                    queue.offer(nums[i]);
                }else if(queue.peek() < nums[i]) {
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
        }

        public int add(int val) {
            if(queue.size() < k) {
                queue.offer(val);
            }
            else if(val > queue.peek()) {
                queue.poll();
                queue.offer(val);
            }
            return queue.peek();
        }
    }

}
